from typing import List

MAX_INT = 30 * 30 * 100 + 1


class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        size = len(stones)

        # 处理无法完成的情况
        if (size - 1) % (k - 1) != 0:
            return -1

        # 计算前缀和
        prefix = [0]
        for i in range(size):
            prefix.append(stones[i] + prefix[-1])

        # 步骤总数
        total_step = (size - 1) // (k - 1)
        # print("步骤总数:", total_step)

        # 定义状态表格：dp[i][j][k] = 将区间[i,j]缩k堆需要的最低成本
        dp = [[[MAX_INT] * (size + 1) for _ in range(size)] for _ in range(size)]

        # 初始化状态矩阵
        for i in range(size):
            for j in range(i, size):
                dp[i][j][j - i + 1] = 0
                # print(i, j, j - i + 1, ":", dp[i][j][j - i + 1])
        for i in range(size - k + 1):
            j = i + k - 1
            dp[i][j][1] = prefix[j + 1] - prefix[i]
            # print(i, j, 1, ":", dp[i][j][1])

        # 状态转移方程：
        # dp[i][j][1] = dp[i][j][k] + sum(i,j)
        # dp[i][j][k] = min{dp[i][p][1] + dp[p+1][j][k-1] + sum(i,j)} i<p<j
        for length in range(k + 1, size + 1):
            # for step in range(2, total_step + 1):
            #     length = 1 + step * (k - 1)
            # print("当前长度", ":", length)
            for i in range(size - length + 1):
                j = i + length - 1
                for m in range(2,k+1):
                    for p in range(i, j):
                        dp[i][j][m] = min(dp[i][j][m], dp[i][p][1] + dp[p + 1][j][m - 1])
                    # print(i, j, m, ":", dp[i][j][m])

                dp[i][j][1] = dp[i][j][k] + prefix[j + 1] - prefix[i]
                # print(i, j, 1, ":", dp[i][j][1])

        return dp[0][size - 1][1]


if __name__ == "__main__":
    print(Solution().mergeStones(stones=[3, 2, 4, 1], k=2))  # 20
    print(Solution().mergeStones(stones=[3, 2, 4, 1], k=3))  # -1
    print(Solution().mergeStones(stones=[3, 5, 1, 2, 6], k=3))  # 25
